<!DOCTYPE html>


<html lang="zh-CN">


<head>
  <meta charset="utf-8" />
  <meta name="baidu-site-verification" content="code-kg5UjKJZM2" />
   
  <meta name="keywords" content="活,炼" />
   
  <meta name="description" content="shimmerjordan" />
  
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
  <title>
    In-depth analysis of Java-HashMap |  丛烨-shimmerjordan
  </title>
  <meta name="generator" content="hexo-theme-ayer">
  
  <link rel="shortcut icon" href="/favicon.ico" />
  
  
<link rel="stylesheet" href="/dist/main.css">

  <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Shen-Yu/cdn/css/remixicon.min.css">
  
<link rel="stylesheet" href="/css/custom.css">

  
  <script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>
  
  

<script type="text/javascript">
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');

ga('create', 'G-Q0DT8B8VJW', 'auto');
ga('send', 'pageview');

</script>



  
<script>
var _hmt = _hmt || [];
(function() {
	var hm = document.createElement("script");
	hm.src = "https://hm.baidu.com/hm.js?6d06f826e125297d4ce0fa7a1449328e";
	var s = document.getElementsByTagName("script")[0]; 
	s.parentNode.insertBefore(hm, s);
})();
</script>


<link rel="alternate" href="/atom.xml" title="丛烨-shimmerjordan" type="application/atom+xml">
</head>

</html>

	<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome/css/font-awesome.min.css">
	<script src="https://cdn.jsdelivr.net/gh/stevenjoezhang/live2d-widget@latest/autoload.js"></script>


<body>
  <div id="app">
    
      
    <main class="content on">
      <section class="outer">
  <article
  id="post-In-depth analysis of Java-HashMap"
  class="article article-type-post"
  itemscope
  itemprop="blogPost"
  data-scroll-reveal
>
  <div class="article-inner">
    
    <header class="article-header">
       
<h1 class="article-title sea-center" style="border-left:0" itemprop="name">
  In-depth analysis of Java-HashMap
</h1>
 

    </header>
     
    <div class="article-meta">
      <a href="/2020/12/03/Java-HashMap/" class="article-date">
  <time datetime="2020-12-03T04:14:18.000Z" itemprop="datePublished">2020-12-03</time>
</a> 
  <div class="article-category">
    <a class="article-category-link" href="/categories/Data-structures/">Data structures</a>
  </div>
  
<div class="word_count">
    <span class="post-time">
        <span class="post-meta-item-icon">
            <i class="ri-quill-pen-line"></i>
            <span class="post-meta-item-text"> 字数统计:</span>
            <span class="post-count">3.6k</span>
        </span>
    </span>

    <span class="post-time">
        &nbsp; | &nbsp;
        <span class="post-meta-item-icon">
            <i class="ri-book-open-line"></i>
            <span class="post-meta-item-text"> 阅读时长≈</span>
            <span class="post-count">22 分钟</span>
        </span>
    </span>
</div>
 
    </div>
      
    <div class="tocbot"></div>




  
    <div class="article-entry" itemprop="articleBody">
       
  <h1 id="Introduction"><a href="#Introduction" class="headerlink" title="Introduction"></a>Introduction</h1><hr>
<p>Hash table is a very important data structure with a rich set of applications. The core of many caching techniques (such as memcached) is actually maintaining a large hash table in memory. This article will explain the principles of HashMap implementation in the java collection framework and analyse the JDK7 HashMap source code.</p>
<span id="more"></span>
<h1 id="1-What-is-HashMap"><a href="#1-What-is-HashMap" class="headerlink" title="1. What is HashMap"></a>1. What is HashMap</h1><p>Before discussing the hash table, we firstly have an overview of the performance of other data structures in performing basic operations such as adding, searching, etc.</p>
<p><strong>Array:</strong> Array uses a continuous segment of memory cells to store data. For a given subscript search,  the time complex is $O(1)$; For a search by a given value, it is necessary to traverse the array, comparing the given keywords and array elements one by one, with a time complex of $O(n)$. Of course, for ordered arrays, the dichotomous search, interpolation search, Fibonacci search, etc. can be used, increasing the complexity of the search for $O(\log n)$; For the general insertion and deletion operations, involving the movement of array elements, the average complexity is also $O(n)$.</p>
<p><strong>Linear chain table:</strong> For the addition, deletion, etc. of a link table (after the location of the specified operation has been found), only the references between the nodes need to be processed, which has a time complexity of $O(1)$, while the search operation needs to traverse the link table one by one for comparison, which has a complexity of $O(n)$.</p>
<p><strong>Binary tree:</strong> The insertion, search and deletion operations carried out on a relatively balanced, ordered binary tree have an average complexity of $O(\log n)$.</p>
<p><strong>Hash tables:</strong> Compared to the data structures above, adding, deleting, searching, etc. in a hash table has very high performance and can be done in just one location, regardless of hash conflicts (which can be discussed later), with a time complexity of $O(1)$. I will show how the hash table is achieved to reach the stunning constant order complexity of $O(1)$.</p>
<p>As we know, there are only two types of physical storage structures for data structures: sequential storage structures (like stacks, queues, trees, graphs, etc. that are abstracted from logical structures and mapped to memory, which are also two forms of physical organisation). As we mentioned above, finding an element in an array based on its subscript can be achieved in a single location. Hash tables make use of this property, the backbone of the hash table being the array.</p>
<p>For example, if we want to add or find an element, we can do this by mapping the current element’s keyword to a location in the array via a  function that locates the array’s subscript once.</p>
<p>This function can be described simply as: store location = $f(keywords)$, this function $f$ is generally known as the hash function, and the design of this function will have a direct impact on the performance of the hash table. As an example, if we want to perform an insert operation in a hash table, whose process is shown in the figure below:</p>
<center>
    <img style="border-radius: 0.3125em;
    box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
    src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed@main/blog/2020/12/04/DqKdIJ.jpg">
    <br>
    <div style="color:orange; border-bottom: 1px solid #d9d9d9;
    display: inline-block;
    color: #999;
    padding: 2px;">Insertion operation</div>
</center>

<p>The same principle applies to the search operation, where the actual storage address is calculated via the hash function and then the corresponding address is retrieved from the array.</p>
<p><strong>Hash conflict:</strong></p>
<p>However, nothing is perfect, so what if two different elements have the same actual storage address via a hash function? In other words, when we perform a hash operation on an element, get a storage address and then, when we want to insert it, we find that it is already occupied by another element. This is in fact a so-called hash conflict, also known as a hash collision. As we have mentioned before, the design of the hash function is crucial. A good hash function will ensure that the calculation is as simple as possible and that the hash address is evenly distributed. So how are hash conflicts resolved? There are various solutions to hash conflicts: the open address method (in the event of a conflict, the search continues for the next unoccupied storage address), the re-hash function method, the chain address method, and HashMap uses the chain address method, which is an array + chain table method.</p>
<h1 id="2-Implementation-principle-of-HashMap"><a href="#2-Implementation-principle-of-HashMap" class="headerlink" title="2. Implementation principle of HashMap"></a>2. Implementation principle of HashMap</h1><p>The backbone of a HashMap is an array of Entries, which are the basic building blocks of a HashMap, each of those containing a key-value pair. (A Map is actually a collection that holds the mapping between two objects.)</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//The backbone array of a HashMap can be seen as an Entry array </span></span><br><span class="line"><span class="comment">//with an initial value of an empty array &#123;&#125;, the length of which must be a power of 2</span></span><br><span class="line"><span class="comment">//The reasons why this was done are analysed in detail later.</span></span><br><span class="line"><span class="keyword">transient</span> Entry&lt;K,V&gt;[] table = (Entry&lt;K,V&gt;[]) EMPTY_TABLE;</span><br></pre></td></tr></table></figure>
<p>Entry is a static internal class in a HashMap. The code is as follows:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">Entry</span>&lt;K,V&gt; <span class="keyword">implements</span> <span class="title class_">Map</span>.Entry&lt;K,V&gt; &#123;</span><br><span class="line">    <span class="keyword">final</span> K key;</span><br><span class="line">    V value;</span><br><span class="line">    Entry&lt;K,V&gt; next;	<span class="comment">//Storing references to the next Entry, single-chain table structure</span></span><br><span class="line">    <span class="type">int</span> hash;	<span class="comment">//The hash code value of the key is hashed and stored in the Entry to avoid double counting.</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">    * Creates new entry.</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">    Entry(<span class="type">int</span> h, K k, V v, Entry&lt;K,V&gt; n) &#123;</span><br><span class="line">        value = v;</span><br><span class="line">        next = n;</span><br><span class="line">        key = k;</span><br><span class="line">        hash = h;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="overall-structure"><a href="#overall-structure" class="headerlink" title="overall structure"></a>overall structure</h2><p>The overall structure of a HashMap is therefore as follows:</p>
<center>
    <img style="border-radius: 0.3125em;
    box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
    src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed@main/blog/2020/12/04/DqG000.png" width='80%'>
    <br>
    <div style="color:orange; border-bottom: 1px solid #d9d9d9;
    display: inline-block;
    color: #999;
    padding: 2px;">Overall structure of a HashMap</div>
</center>

<p>Put it simply, a HashMap consists of an array + a linked table. The array is the main body of the HashMap, while the linked table exists mainly to resolve hash conflicts. For the search  operation, the link table still needs to be traversed, and then the key object’s equals method can be used to find the link table one by one. Therefore, in terms of performance, the less the link table appears in a HashMap, the better the performance will be.</p>
<h2 id="A-few-other-important-fields"><a href="#A-few-other-important-fields" class="headerlink" title="A few other important fields"></a>A few other important fields</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/* Number of key-value pairs actually stored */</span></span><br><span class="line"><span class="keyword">transient</span> <span class="type">int</span> size;</span><br><span class="line"></span><br><span class="line"><span class="comment">/** Threshold value, which is the initial capacity when table == &#123;&#125; </span></span><br><span class="line"><span class="comment">* (the default initial capacity is 16); </span></span><br><span class="line"><span class="comment">* when table is filled, i.e. when memory space has been allocated to it.</span></span><br><span class="line"><span class="comment">* HashMap needs to refer to the threshold when scaling, </span></span><br><span class="line"><span class="comment">* which is discussed in more detail later</span></span><br><span class="line"><span class="comment">*/</span>.</span><br><span class="line"><span class="type">int</span> threshold;</span><br><span class="line"></span><br><span class="line"><span class="comment">/** load factor, which represents how much the table is filled, the default is 0.75</span></span><br><span class="line"><span class="comment">* The reason for the load factor is also to mitigate hash conflicts, </span></span><br><span class="line"><span class="comment">* because if the initial bucket is 16 and you wait until it is full of 16 elements before expanding, </span></span><br><span class="line"><span class="comment">* some buckets may have more than one element in them.</span></span><br><span class="line"><span class="comment">* So the default loading factor is 0.75, </span></span><br><span class="line"><span class="comment">* which means that a HashMap of size 16 will expand to 32 by the 13th element.</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">final</span> <span class="type">float</span> loadFactor;</span><br><span class="line"></span><br><span class="line"><span class="comment">/** The number of times the HashMap has been changed, </span></span><br><span class="line"><span class="comment">* due to the non-threaded safety of the HashMap, when iterating on the HashMap</span></span><br><span class="line"><span class="comment">* If the structure of the HashMap has changed during the period due to the involvement of other threads (e.g. put, remove, etc.).</span></span><br><span class="line"><span class="comment">* A ConcurrentModificationException needs to be thrown</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">transient</span> <span class="type">int</span> modCount;</span><br></pre></td></tr></table></figure>
<h2 id="constructors"><a href="#constructors" class="headerlink" title="constructors"></a>constructors</h2><p>HashMap has four constructors, the other constructors use default values if the user does not pass in the <em>initialCapacity</em> and <em>loadFactor</em> parameters.</p>
<p>The default <em>initialCapacity</em> is 16 and the default <em>loadFactory</em> is 0.75.</p>
<p>Let’s take a look at one of these:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="title function_">HashMap</span><span class="params">(<span class="type">int</span> initialCapacity, <span class="type">float</span> loadFactor)</span> &#123;</span><br><span class="line">	<span class="comment">//Here the incoming initial capacity is verified </span></span><br><span class="line">    <span class="comment">//and cannot exceed a maximum of MAXIMUM_CAPACITY = 1&lt;&lt;30(230)</span></span><br><span class="line">	<span class="keyword">if</span> (initialCapacity &lt; <span class="number">0</span>)</span><br><span class="line">	<span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">IllegalArgumentException</span>(<span class="string">&quot;Illegal initial capacity: &quot;</span> +</span><br><span class="line">                                               initialCapacity);</span><br><span class="line">	<span class="keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">		initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line">	<span class="keyword">if</span> (loadFactor &lt;= <span class="number">0</span> || Float.isNaN(loadFactor))</span><br><span class="line">		<span class="keyword">throw</span> <span class="keyword">new</span> <span class="title class_">IllegalArgumentException</span>(<span class="string">&quot;Illegal load factor: &quot;</span> +</span><br><span class="line">                                               loadFactor);</span><br><span class="line"></span><br><span class="line">	<span class="built_in">this</span>.loadFactor = loadFactor;</span><br><span class="line">	threshold = initialCapacity;</span><br><span class="line">　　　　　</span><br><span class="line">	init();<span class="comment">//The init method is not actually implemented in the HashMap, </span></span><br><span class="line">    	   <span class="comment">//but is implemented in its subclasses such as linkedHashMap.</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h2 id="put-operation"><a href="#put-operation" class="headerlink" title="put operation"></a>put operation</h2><p>Let’s now look at the implementation of the put operation:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> V <span class="title function_">put</span><span class="params">(K key, V value)</span> &#123;</span><br><span class="line">	<span class="comment">//If the table array is empty &#123;&#125;, </span></span><br><span class="line">    <span class="comment">//the array is filled (allocating actual memory space to the table),</span></span><br><span class="line">    <span class="comment">//with threshold as the input reference.</span></span><br><span class="line">	<span class="comment">//In this case the threshold is the initialCapacity.&lt;default is 1&lt;&lt;4 (24=16)&gt;</span></span><br><span class="line">	<span class="keyword">if</span> (table == EMPTY_TABLE) &#123;</span><br><span class="line">		inflateTable(threshold);</span><br><span class="line">	&#125;</span><br><span class="line">   <span class="comment">//If the key is null, the storage location is table[0] or on the conflicting chain of table[0].</span></span><br><span class="line">	<span class="keyword">if</span> (key == <span class="literal">null</span>)</span><br><span class="line">		<span class="keyword">return</span> putForNullKey(value);</span><br><span class="line">	<span class="type">int</span> <span class="variable">hash</span> <span class="operator">=</span> hash(key);<span class="comment">//The hashcode of the key is further calculated to ensure an even hash.</span></span><br><span class="line">	<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> indexFor(hash, table.length);<span class="comment">//Get the actual position in the table</span></span><br><span class="line">	<span class="keyword">for</span> (Entry&lt;K,V&gt; e = table[i]; e != <span class="literal">null</span>; e = e.next) &#123;</span><br><span class="line">	<span class="comment">//If this corresponding data already exists, </span></span><br><span class="line">    <span class="comment">//an overwrite is performed. Replace the old value with the new value and return the old value</span></span><br><span class="line">		Object k;</span><br><span class="line">		<span class="keyword">if</span> (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) &#123;</span><br><span class="line">			<span class="type">V</span> <span class="variable">oldValue</span> <span class="operator">=</span> e.value;</span><br><span class="line">			e.value = value;</span><br><span class="line">			e.recordAccess(<span class="built_in">this</span>);</span><br><span class="line">			<span class="keyword">return</span> oldValue;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	modCount++;	<span class="comment">//Guaranteed failure of rapid response if the internal structure of the HashMap changes during concurrent accesses</span></span><br><span class="line">	addEntry(hash, key, value, i);<span class="comment">//Adding an entry</span></span><br><span class="line">	<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>The <em>inflateTable</em> method is used to allocate storage space in memory for the master array table. By <em>roundUpToPowerOf2</em> (toSize) you can ensure that the capacity is greater than or equal to the nearest power of toSize, e.g. toSize=13, then capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title function_">inflateTable</span><span class="params">(<span class="type">int</span> toSize)</span> &#123;</span><br><span class="line">	<span class="type">int</span> <span class="variable">capacity</span> <span class="operator">=</span> roundUpToPowerOf2(toSize);	<span class="comment">//capacity must be a power of 2</span></span><br><span class="line">	<span class="comment">/**Here is the threshold assignment, taking the minimum value of capacity*loadFactor and MAXIMUM_CAPACITY+1.</span></span><br><span class="line"><span class="comment">	* The capaticy must not exceed MAXIMUM_CAPACITY, unless the loadFactor is greater than 1.</span></span><br><span class="line"><span class="comment">	*/</span></span><br><span class="line">	threshold = (<span class="type">int</span>) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + <span class="number">1</span>);</span><br><span class="line">	table = <span class="keyword">new</span> <span class="title class_">Entry</span>[capacity];</span><br><span class="line">	initHashSeedAsNeeded(capacity);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>The processing in <em>roundUpToPowerOf2</em> is such that the length of the array must be a power of 2. <em>Integer.highestOneBit</em> is used to get the value represented by the leftmost bit (the other bits are 0).</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">roundUpToPowerOf2</span><span class="params">(<span class="type">int</span> number)</span> &#123;</span><br><span class="line">	<span class="comment">// assert number &gt;= 0 : &quot;number must be non-negative&quot;;</span></span><br><span class="line">	<span class="keyword">return</span> number &gt;= MAXIMUM_CAPACITY</span><br><span class="line">			? MAXIMUM_CAPACITY</span><br><span class="line">			: (number &gt; <span class="number">1</span>) ? Integer.highestOneBit((number - <span class="number">1</span>) &lt;&lt; <span class="number">1</span>) : <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>Hash function</strong></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**This is a magic function that uses a lot of isomorphisms, transpositions, etc.</span></span><br><span class="line"><span class="comment">* Further calculations of the key&#x27;s hashcode and adjustment of the binary bits ensure that </span></span><br><span class="line"><span class="comment">* the resulting storage locations are as evenly distributed as possible.</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">final</span> <span class="type">int</span> <span class="title function_">hash</span><span class="params">(Object k)</span> &#123;</span><br><span class="line">	<span class="type">int</span> <span class="variable">h</span> <span class="operator">=</span> hashSeed;</span><br><span class="line">	<span class="keyword">if</span> (<span class="number">0</span> != h &amp;&amp; k <span class="keyword">instanceof</span> String) &#123;</span><br><span class="line">		<span class="keyword">return</span> sun.misc.Hashing.stringHash32((String) k);</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	h ^= k.hashCode();</span><br><span class="line"></span><br><span class="line">	h ^= (h &gt;&gt;&gt; <span class="number">20</span>) ^ (h &gt;&gt;&gt; <span class="number">12</span>);</span><br><span class="line">	<span class="keyword">return</span> h ^ (h &gt;&gt;&gt; <span class="number">7</span>) ^ (h &gt;&gt;&gt; <span class="number">4</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>The value calculated by the above hash function is further processed by indexFor to obtain the actual storage location.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * return the index of array</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">static</span> <span class="type">int</span> <span class="title function_">indexFor</span><span class="params">(<span class="type">int</span> h, <span class="type">int</span> length)</span> &#123;</span><br><span class="line">	<span class="keyword">return</span> h &amp; (length-<span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>h&amp;(length-1) ensures that the index obtained is within the array, for example, the default capacity is 16, length-1=15, h=18, which is converted to binary as index=2. Bit operations are much higher performance for computers (there are a lot of bit operations in HashMap).</p>
<p>So the process for determining the final storage location is as follows.</p>
<center>
    <img style="border-radius: 0.3125em;
    box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
    src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed@main/blog/2020/12/05/DOrEhd.jpg">
    <br>
    <div style="color:orange; border-bottom: 1px solid #d9d9d9;
    display: inline-block;
    color: #999;
    padding: 2px;">process for determining</div>
</center>

<p>A further look at the implementation of addEntry:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> <span class="title function_">addEntry</span><span class="params">(<span class="type">int</span> hash, K key, V value, <span class="type">int</span> bucketIndex)</span> &#123;</span><br><span class="line">	<span class="keyword">if</span> ((size &gt;= threshold) &amp;&amp; (<span class="literal">null</span> != table[bucketIndex])) &#123;</span><br><span class="line">		resize(<span class="number">2</span> * table.length);	<span class="comment">//Scaling when size exceeds the critical threshold and a hash conflict is imminent</span></span><br><span class="line">		hash = (<span class="literal">null</span> != key) ? hash(key) : <span class="number">0</span>;</span><br><span class="line">		bucketIndex = indexFor(hash, table.length);</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	createEntry(hash, key, value, bucketIndex);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>We can learn from the code above that when a hash conflict occurs and the size is greater than the threshold, we need to expand the array. When expanding, we need to create a new array twice the length of the previous one, and the transfer all elements of the current Entry array. The new array is twice the length of the previous after expansion, so expansion is relatively resource-consuming operation.</p>
<h1 id="3-Why-must-the-array-length-of-a-HashMap-be-the-power-of-2"><a href="#3-Why-must-the-array-length-of-a-HashMap-be-the-power-of-2" class="headerlink" title="3. Why must the array length of a HashMap be the power of 2"></a>3. Why must the array length of a HashMap be the power of 2</h1><p>Let’s continue analysis the resize method above:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> <span class="title function_">resize</span><span class="params">(<span class="type">int</span> newCapacity)</span> &#123;</span><br><span class="line">	Entry[] oldTable = table;</span><br><span class="line">	<span class="type">int</span> <span class="variable">oldCapacity</span> <span class="operator">=</span> oldTable.length;</span><br><span class="line">	<span class="keyword">if</span> (oldCapacity == MAXIMUM_CAPACITY) &#123;</span><br><span class="line">		threshold = Integer.MAX_VALUE;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	Entry[] newTable = <span class="keyword">new</span> <span class="title class_">Entry</span>[newCapacity];</span><br><span class="line">	transfer(newTable, initHashSeedAsNeeded(newCapacity));</span><br><span class="line">	table = newTable;</span><br><span class="line">	threshold = (<span class="type">int</span>)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + <span class="number">1</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>If the array is expanded, the length of the array changes and the storage location index = h&amp;(length-1),index may also change and the index needs to be recalculated, let’s look at the transfer method first.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">void</span> <span class="title function_">transfer</span><span class="params">(Entry[] newTable, <span class="type">boolean</span> rehash)</span> &#123;</span><br><span class="line">	<span class="type">int</span> <span class="variable">newCapacity</span> <span class="operator">=</span> newTable.length;</span><br><span class="line">    <span class="comment">//The code in the for loop goes through the chain table one by one, </span></span><br><span class="line">    <span class="comment">//recalculating the index positions and copying the old array data into the new array </span></span><br><span class="line">    <span class="comment">//(the array does not store the actual data, so it&#x27;s just a copy reference)</span></span><br><span class="line">	<span class="keyword">for</span> (Entry&lt;K,V&gt; e : table) &#123;</span><br><span class="line">		<span class="keyword">while</span>(<span class="literal">null</span> != e) &#123;</span><br><span class="line">			Entry&lt;K,V&gt; next = e.next;</span><br><span class="line">			<span class="keyword">if</span> (rehash) &#123;</span><br><span class="line">				e.hash = <span class="literal">null</span> == e.key ? <span class="number">0</span> : hash(e.key);</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> indexFor(e.hash, newCapacity);</span><br><span class="line">			<span class="comment">//Point the next chain of the current entry to the new index position,</span></span><br><span class="line">            <span class="comment">//newTable[i] may be empty, or it may also be an entry chain,</span></span><br><span class="line">            <span class="comment">//in which case it is inserted directly at the head of the chain table.</span></span><br><span class="line">			e.next = newTable[i];</span><br><span class="line">			newTable[i] = e;</span><br><span class="line">			e = next;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>This method takes the data from the old array and traverses it one by one, chain by chain, throwing it into the new expanded array. The array index position is calculated by hash scrambling the key value hashcode and then performing a bitwise operation with length-1 to obtain the final array index position.</p>
<p>For example, if the binary representation of 16 is 10000, then length-1 is 15, and the binary is 01111, similarly the expanded array length is 32, binary is 100000, length-1 is 31, and the binary is 011111. It is guaranteed that the low bit is all 1, while the expansion has only one difference, i.e. an extra leftmost 1, so that when passing h&amp;(length-1), as long as the leftmost difference bit corresponding to h is 0, the new array index is guaranteed to be the same as the old one (greatly reducing the need to re-swap the data position of the old array which has been well hashed before), with personal understanding.</p>
<center>
    <img style="border-radius: 0.3125em;
    box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
    src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed@main/blog/2020/12/06/DXzISg.jpg">
    <br>
    <div style="color:orange; border-bottom: 1px solid #d9d9d9;
    display: inline-block;
    color: #999;
    padding: 2px;">length of HashMap array</div>
</center>

<p>Also, keeping the length of the array to the power of 2, with the lower bits of length-1 all being 1, results in a more uniform index of the obtained array.</p>
<center>
    <img style="border-radius: 0.3125em;
    box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
    src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed@main/blog/2020/12/06/DjS79O.jpg">
    <br>
    <div style="color:orange; border-bottom: 1px solid #d9d9d9;
    display: inline-block;
    color: #999;
    padding: 2px;">length of HashMap array</div>
</center>

<p>As we can see, with the &amp; operation above, the higher bits have no effect on the result (the hash function uses a variety of bit operations, possibly also to make the lower bits more hashed), we are only concerned with the lower bits, and if the lower bits are all 1, then for the lower part of h, any change in one bit will have an effect on the result, i.e. to get to the storage position index=21, h’s This is the only combination of the lower positions. This is the reason why the array length is designed so that it must be a power of 2.</p>
<center>
    <img style="border-radius: 0.3125em;
    box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
    src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed@main/blog/2020/12/06/Dj9JyQ.jpg">
    <br>
    <div style="color:orange; border-bottom: 1px solid #d9d9d9;
    display: inline-block;
    color: #999;
    padding: 2px;">length of HashMap array</div>
</center>

<p>If it is not the power of 2, i.e. the low bit is not all 1, then, to make index = 21, the low part of h is no longer unique and the chance of a hash conflict becomes even greater. At the same time, the bit corresponding to the index will not be equal to 1 in any case, and the corresponding array positions will be wasted.</p>
<h2 id="get-method"><a href="#get-method" class="headerlink" title="get method"></a>get method</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"> <span class="keyword">public</span> V <span class="title function_">get</span><span class="params">(Object key)</span> &#123;</span><br><span class="line">　　<span class="comment">//If the key is null, then just go to table[0] to retrieve it.</span></span><br><span class="line">	<span class="keyword">if</span> (key == <span class="literal">null</span>)</span><br><span class="line">		<span class="keyword">return</span> getForNullKey();</span><br><span class="line">	Entry&lt;K,V&gt; entry = getEntry(key);</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">null</span> == entry ? <span class="literal">null</span> : entry.getValue();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>The get method returns the corresponding value by means of a key, and if the key is null, it goes directly to table[0]. Let’s look at the getEntry method again</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">final</span> Entry&lt;K,V&gt; <span class="title function_">getEntry</span><span class="params">(Object key)</span> &#123;</span><br><span class="line">            </span><br><span class="line">	<span class="keyword">if</span> (size == <span class="number">0</span>) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//Calculation of the hash value via the key&#x27;s hashcode value</span></span><br><span class="line">	<span class="type">int</span> <span class="variable">hash</span> <span class="operator">=</span> (key == <span class="literal">null</span>) ? <span class="number">0</span> : hash(key);</span><br><span class="line">	<span class="comment">//indexFor (hash&amp;length-1) gets the final array index and then traverses the chain table </span></span><br><span class="line">    <span class="comment">//to find the corresponding records by matching them with the equals method</span></span><br><span class="line">	<span class="keyword">for</span> (Entry&lt;K,V&gt; e = table[indexFor(hash, table.length)];</span><br><span class="line">		 e != <span class="literal">null</span>;</span><br><span class="line">		 e = e.next) &#123;</span><br><span class="line">		Object k;</span><br><span class="line">		<span class="keyword">if</span> (e.hash == hash &amp;&amp; </span><br><span class="line">			((k = e.key) == key || (key != <span class="literal">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">			<span class="keyword">return</span> e;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">&#125;    </span><br></pre></td></tr></table></figure>
<p>As can be seen, the get method is relatively simple to implement, key(hashcode)-&gt;hash-&gt;indexFor-&gt;final index position, find the corresponding position table[i], check if there is a link table, traverse the link table, and pass the key’s The equals method compares and finds the corresponding record. It is important to note that some people feel that the above judgement of e.hash == hash is not necessary when traversing the chain table after locating the array position and then using only the equals judgement. This is not the case, think about it, if the incoming key object overrides the equals method but does not override the hashCode, and it happens that this object is positioned in this array, if only using equals may be equal, but its hashCode is not consistent with the current object, in this case, according to the conventions of Object’s hashCode, can not return Instead of the current object, null should be returned, as will be further explained in the examples that follow.</p>
<h1 id="4-Overriding-the-equals-method-requires-overriding-the-hashCode-method"><a href="#4-Overriding-the-equals-method-requires-overriding-the-hashCode-method" class="headerlink" title="4. Overriding the equals method requires overriding the hashCode method."></a>4. Overriding the equals method requires overriding the hashCode method.</h1><p>Finally we come to the age-old question, which is mentioned in various sources, “overwrite the hashcode as well as the equals”. Let’s take a small example to see what happens if we override equals without overriding the hashcode.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">MyTest</span> &#123;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">class</span> <span class="title class_">Person</span>&#123;</span><br><span class="line">        <span class="type">int</span> idCard;</span><br><span class="line">        String name;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">public</span> <span class="title function_">Person</span><span class="params">(<span class="type">int</span> idCard, String name)</span> &#123;</span><br><span class="line">            <span class="built_in">this</span>.idCard = idCard;</span><br><span class="line">            <span class="built_in">this</span>.name = name;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="meta">@Override</span></span><br><span class="line">        <span class="keyword">public</span> <span class="type">boolean</span> <span class="title function_">equals</span><span class="params">(Object o)</span> &#123;</span><br><span class="line">            <span class="keyword">if</span> (<span class="built_in">this</span> == o) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (o == <span class="literal">null</span> || getClass() != o.getClass())&#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="type">Person</span> <span class="variable">person</span> <span class="operator">=</span> (Person) o;</span><br><span class="line">            <span class="comment">//两个对象是否等值，通过idCard来确定</span></span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">this</span>.idCard == person.idCard;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String []args)</span>&#123;</span><br><span class="line">        HashMap&lt;Person,String&gt; map = <span class="keyword">new</span> <span class="title class_">HashMap</span>&lt;Person, String&gt;();</span><br><span class="line">        <span class="type">Person</span> <span class="variable">person</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Person</span>(<span class="number">1234</span>,<span class="string">&quot;乔峰&quot;</span>);</span><br><span class="line">        <span class="comment">//put到hashmap中去</span></span><br><span class="line">        map.put(person,<span class="string">&quot;天龙八部&quot;</span>);</span><br><span class="line">        <span class="comment">//get取出，从逻辑上讲应该能输出“天龙八部”</span></span><br><span class="line">        System.out.println(<span class="string">&quot;结果:&quot;</span>+map.get(<span class="keyword">new</span> <span class="title class_">Person</span>(<span class="number">1234</span>,<span class="string">&quot;萧峰&quot;</span>)));</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<pre><code>实际输出结果：null
</code></pre><p>This result is easy to understand if we already have some understanding of the principles of HashMap. Although the keys we use for the get and put operations are logically equivalent (equal by comparison with equals), there is no overriding of the hashCode method, so that for the put operation, key(hashcode1)-&gt;hash-&gt; indexFor-&gt;final index position. Whereas when retrieving values by key key(hashcode1)-&gt;hash-&gt;indexFor-&gt;final index position, as hashcode1 is not equal to hashcode2, an array of positions is not located and the value is not retrieved. The logically incorrect value null is returned (it is also possible to happen to locate an array of positions. But it also determines whether its entry hash value is equal, as mentioned in the get method above).</p>
<p>So, when rewriting the methods of equals, care must be taken to rewrite the hashCode method. It is also important to ensure that calls to the hashCode method return the same integer value for two objects that are judged to be equal by equals. If the equals judge two objects that are not equal, the hashCode can be the same (hash conflicts will occur and should be avoided).</p>
<h1 id="5-Performance-optimisation-of-HashMap-in-JDK-1-8"><a href="#5-Performance-optimisation-of-HashMap-in-JDK-1-8" class="headerlink" title="5. Performance optimisation of HashMap in JDK 1.8"></a>5. Performance optimisation of HashMap in JDK 1.8</h1><p>What if there is too much data on an array of slots on the chain (i.e. the zip is too long) causing a drop in performance?<br>JDK1.8 has added a red and black tree on the basis of JDK1.7 to optimise the HashMap. That is to say, when the chain table exceeds 8, the chain table will be converted into a red and black tree to improve the performance of HashMap by taking advantage of the rapid addition, deletion and rechecking of the red and black tree, in which the insertion, deletion and search algorithms of the red and black tree will be used.</p>
<h1 id="Attachment-HashMap-put-method-logic-diagram-JDK-1-8"><a href="#Attachment-HashMap-put-method-logic-diagram-JDK-1-8" class="headerlink" title="Attachment: HashMap put method logic diagram (JDK 1.8)"></a>Attachment: HashMap put method logic diagram (JDK 1.8)</h1><center>
    <img style="border-radius: 0.3125em;
    box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);" 
    src="https://gcore.jsdelivr.net/gh/shimmerjordan/pic_bed@main/blog/2020/12/06/DjEVhR.png">
    <br>
    <div style="color:orange; border-bottom: 1px solid #d9d9d9;
    display: inline-block;
    color: #999;
    padding: 2px;">logic diagram of put method</div>
</center> 
      <!-- reward -->
      
      <div id="reword-out">
        <div id="reward-btn">
          打赏
        </div>
      </div>
      
    </div>
    

    <!-- copyright -->
    
    <div class="declare">
      <ul class="post-copyright">
        <li>
          <i class="ri-copyright-line"></i>
          <strong>版权声明： </strong>
          
          本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
          
        </li>
      </ul>
    </div>
    
    <footer class="article-footer">
       
<div class="share-btn">
      <span class="share-sns share-outer">
        <i class="ri-share-forward-line"></i>
        分享
      </span>
      <div class="share-wrap">
        <i class="arrow"></i>
        <div class="share-icons">
          
          <a class="weibo share-sns" href="javascript:;" data-type="weibo">
            <i class="ri-weibo-fill"></i>
          </a>
          <a class="weixin share-sns wxFab" href="javascript:;" data-type="weixin">
            <i class="ri-wechat-fill"></i>
          </a>
          <a class="qq share-sns" href="javascript:;" data-type="qq">
            <i class="ri-qq-fill"></i>
          </a>
          <a class="douban share-sns" href="javascript:;" data-type="douban">
            <i class="ri-douban-line"></i>
          </a>
          <!-- <a class="qzone share-sns" href="javascript:;" data-type="qzone">
            <i class="icon icon-qzone"></i>
          </a> -->
          
          <a class="facebook share-sns" href="javascript:;" data-type="facebook">
            <i class="ri-facebook-circle-fill"></i>
          </a>
          <a class="twitter share-sns" href="javascript:;" data-type="twitter">
            <i class="ri-twitter-fill"></i>
          </a>
          <a class="google share-sns" href="javascript:;" data-type="google">
            <i class="ri-google-fill"></i>
          </a>
        </div>
      </div>
</div>

<div class="wx-share-modal">
    <a class="modal-close" href="javascript:;"><i class="ri-close-circle-line"></i></a>
    <p>扫一扫，分享到微信</p>
    <div class="wx-qrcode">
      <img src="//api.qrserver.com/v1/create-qr-code/?size=150x150&data=https://blog.shimmerjordan.eu.org/2020/12/03/Java-HashMap/" alt="微信分享二维码">
    </div>
</div>

<div id="share-mask"></div>  
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Data-structures/" rel="tag">Data structures</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/HashMap/" rel="tag">HashMap</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/Java/" rel="tag">Java</a></li></ul>

    </footer>
  </div>

   
  <nav class="article-nav">
    
      <a href="/2020/12/06/HashMap-HashTable/" class="article-nav-link">
        <strong class="article-nav-caption">上一篇</strong>
        <div class="article-nav-title">
          
            Differences between HashMap and HashTable
          
        </div>
      </a>
    
    
      <a href="/2020/11/08/WatermarkRemoval/" class="article-nav-link">
        <strong class="article-nav-caption">下一篇</strong>
        <div class="article-nav-title">A Possible Way to Remove Watermark perfectly</div>
      </a>
    
  </nav>

   
<!-- valine评论 -->
<div id="vcomments-box">
  <div id="vcomments"></div>
</div>
<script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/valine@1.4.14/dist/Valine.min.js"></script>
<script>
  new Valine({
    el: "#vcomments",
    app_id: "StYfTMDp78X0EltFR16ve2q5-gzGzoHsz",
    app_key: "G4RPxRpXG6RwdfpnJefOSnyy",
    path: window.location.pathname,
    avatar: "wavatar",
    placeholder: "ヾﾉ≧∀≦)o来啊，快活啊!",
    recordIP: true,
  });
  const infoEle = document.querySelector("#vcomments .info");
  if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
    infoEle.childNodes.forEach(function (item) {
      item.parentNode.removeChild(item);
    });
  }
</script>
<style>
  #vcomments-box {
    padding: 5px 30px;
  }

  @media screen and (max-width: 800px) {
    #vcomments-box {
      padding: 5px 0px;
    }
  }

  #vcomments-box #vcomments {
    background-color: #fff;
  }

  .v .vlist .vcard .vh {
    padding-right: 20px;
  }

  .v .vlist .vcard {
    padding-left: 10px;
  }
</style>

 
   
   
<!-- minivaline评论 -->
<div id="mvcomments-box">
  <div id="mvcomments"></div>
</div>
<script src="https://cdn.jsdelivr.net/npm/minivaline@latest"></script>
<script>
    new MiniValine(Object.assign({"enable":true,"mode":"DesertsP","placeholder":"Write a Comment","math":true,"md":true,"enableQQ":true,"NoRecordIP":false,"visitor":true,"maxNest":6,"pageSize":6,"adminEmailMd5":"de8a7aa53d07e6b6bceb45c64027763d","tagMeta":["管理员","小伙伴","访客"],"master":["de8a7aa53d07e6b6bceb45c64027763d"],"friends":["b5bd5d836c7a0091aa8473e79ed4c25e","adb7d1cd192658a55c0ad22a3309cecf","3ce1e6c77b4910f1871106cb30dc62b0","cfce8dc43725cc14ffcd9fb4892d5bfc"],"lang":null,"emoticonUrl":["https://cdn.jsdelivr.net/npm/alus@latest","https://cdn.jsdelivr.net/gh/MiniValine/qq@latest","https://cdn.jsdelivr.net/gh/MiniValine/Bilibilis@latest","https://cdn.jsdelivr.net/gh/MiniValine/tieba@latest","https://cdn.jsdelivr.net/gh/MiniValine/twemoji@latest","https://cdn.jsdelivr.net/gh/MiniValine/weibo@latest"]}, {
	  el: '#mvcomments',
    }));
  const infoEle = document.querySelector('#mvcomments .info');
  if (infoEle && infoEle.childNodes && infoEle.childNodes.length > 0) {
      infoEle.childNodes.forEach(function (item) {
          item.parentNode.removeChild(item);
      });
  }
</script>
<style>
	#mvcomments-box {
		padding: 5px 30px;
	}
	@media screen and (max-width: 800px) {
		#mvcomments-box {
		  padding: 5px 0px;
		}
	}
	.darkmode .MiniValine *{
		color: #f1f1f1!important;
	}
	.darkmode .commentTrigger{
		background-color: #403e3e !important;
	  }
	.darkmode .MiniValine .vpage .more{
		background: #21232F
	}
	.darkmode img{
		filter: brightness(30%)
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment.expand:before{
		background: linear-gradient(180deg, rgba(246,246,246,0), rgba(0,0,0,0.9))
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment.expand:after{
		background: rgba(0,0,0,0.9)
	}
	.darkmode .MiniValine .vlist .vcard .vcomment-body .text-wrapper .vcomment pre{
		background: #282c34
		border: 1px solid #282c34
	}
	.darkmode .MiniValine .vinputs-area .textarea-wrapper textarea{
		color: #000;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper input{
		color: #000;
	}
	.darkmode .MiniValine .vinputs-area .vextra-area .vsmile-icons{
		background: transparent;
	}
	.darkmode .MiniValine .vinputs-wrap{
		border-color: #b2b2b5;
	}
	.darkmode .MiniValine .vinputs-wrap:hover{
		border: 1px dashed #2196f3;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper{
		border-bottom: 1px dashed #b2b2b5;
	}
	.darkmode .MiniValine .vinputs-area .auth-section .input-wrapper:hover{
		border-bottom: 1px dashed #2196f3;
	}
	.darkmode .MiniValine .vbtn{
		background-color: transparent!important;
	}
	.darkmode .MiniValine .vbtn:hover{
		border: 1px dashed #2196f3;
	}
</style>

    
</article>

</section>
      <footer class="footer">
  <div class="outer">
    <ul>
      <li>
        Copyrights &copy;
        2019-2024
        <i class="ri-heart-fill heart_icon"></i> 鞠桥丹-QIAODAN JU
      </li>
    </ul>
    <ul>
      <li>
        
        
        
        由 <a href="https://hexo.io" target="_blank">Hexo</a> 强力驱动
        <span class="division">|</span>
        主题 - <a href="https://github.com/Shen-Yu/hexo-theme-ayer" target="_blank">Ayer</a>
        
      </li>
    </ul>
    <ul>
      <li>
        
        
        <span>
  <span><i class="ri-user-3-fill"></i>访问人数:<span id="busuanzi_value_site_uv"></span></s>
  <span class="division">|</span>
  <span><i class="ri-eye-fill"></i>浏览次数:<span id="busuanzi_value_page_pv"></span></span>
</span>
        
      </li>
    </ul>
    <ul>
      
    </ul>
    <ul>
      
    </ul>
    <ul>
      <li>
        <!-- cnzz统计 -->
        
        <script type="text/javascript" src='https://s4.cnzz.com/z_stat.php?id=1279035150&amp;web_id=1279035150'></script>
        
      </li>
    </ul>
  </div>
</footer>
      <div class="float_btns">
        <div class="totop" id="totop">
  <i class="ri-arrow-up-line"></i>
</div>

<div class="todark" id="todark">
  <i class="ri-moon-line"></i>
</div>

      </div>
    </main>
    <aside class="sidebar on">
      <button class="navbar-toggle"></button>
<nav class="navbar">
  
  <div class="logo">
    <a href="/"><img src="/images/ayer-side.svg" alt="丛烨-shimmerjordan"></a>
  </div>
  
  <ul class="nav nav-main">
    
    <li class="nav-item">
      <a class="nav-item-link" href="/">Home</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/archives">Catalogue</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags">Tags</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/tags/%E9%9A%8F%E7%AC%94/">Essay</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/categories">Archives</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/friends">Friends</a>
    </li>
    
    <li class="nav-item">
      <a class="nav-item-link" href="/2020/01/18/about">About</a>
    </li>
    
  </ul>
</nav>
<nav class="navbar navbar-bottom">
  <ul class="nav">
    <li class="nav-item">
      
      <a class="nav-item-link nav-item-search"  title="搜索">
        <i class="ri-search-line"></i>
      </a>
      
      
      <a class="nav-item-link" target="_blank" href="/atom.xml" title="RSS Feed">
        <i class="ri-rss-line"></i>
      </a>
      
    </li>
  </ul>
</nav>
<div class="search-form-wrap">
  <div class="local-search local-search-plugin">
  <input type="search" id="local-search-input" class="local-search-input" placeholder="Search...">
  <div id="local-search-result" class="local-search-result"></div>
</div>
</div>
    </aside>
    <script>
      if (window.matchMedia("(max-width: 768px)").matches) {
        document.querySelector('.content').classList.remove('on');
        document.querySelector('.sidebar').classList.remove('on');
      }
    </script>
    <div id="mask"></div>

<!-- #reward -->
<div id="reward">
  <span class="close"><i class="ri-close-line"></i></span>
  <p class="reward-p"><i class="ri-cup-line"></i>请我喝杯蓝莓汁吧~</p>
  <div class="reward-box">
    
    <div class="reward-item">
      <img class="reward-img" src="/images/alipay.jpg">
      <span class="reward-type">支付宝</span>
    </div>
    
    
    <div class="reward-item">
      <img class="reward-img" src="/images/wechat.jpg">
      <span class="reward-type">微信</span>
    </div>
    
  </div>
</div>
    
<script src="/js/jquery-2.0.3.min.js"></script>


<script src="/js/lazyload.min.js"></script>

<!-- Tocbot -->


<script src="/js/tocbot.min.js"></script>

<script>
  tocbot.init({
    tocSelector: '.tocbot',
    contentSelector: '.article-entry',
    headingSelector: 'h1, h2, h3, h4, h5, h6',
    hasInnerContainers: true,
    scrollSmooth: true,
    scrollContainer: 'main',
    positionFixedSelector: '.tocbot',
    positionFixedClass: 'is-position-fixed',
    fixedSidebarOffset: 'auto'
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.js"></script>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/jquery-modal@0.9.2/jquery.modal.min.css">
<script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js"></script>

<script src="/dist/main.js"></script>

<!-- ImageViewer -->

<!-- Root element of PhotoSwipe. Must have class pswp. -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    <!-- Background of PhotoSwipe. 
         It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>

    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">

        <!-- Container that holds slides. 
            PhotoSwipe keeps only 3 of them in the DOM to save memory.
            Don't modify these 3 pswp__item elements, data is added later on. -->
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                <!--  Controls are self-explanatory. Order can be changed. -->

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" style="display:none" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
                <!-- element will get class pswp__preloader--active when preloader is running -->
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.min.css">
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"></script>

<script>
    function viewer_init() {
        let pswpElement = document.querySelectorAll('.pswp')[0];
        let $imgArr = document.querySelectorAll(('.article-entry img:not(.reward-img)'))

        $imgArr.forEach(($em, i) => {
            $em.onclick = () => {
                // slider展开状态
                // todo: 这样不好，后面改成状态
                if (document.querySelector('.left-col.show')) return
                let items = []
                $imgArr.forEach(($em2, i2) => {
                    let img = $em2.getAttribute('data-idx', i2)
                    let src = $em2.getAttribute('data-target') || $em2.getAttribute('src')
                    let title = $em2.getAttribute('alt')
                    // 获得原图尺寸
                    const image = new Image()
                    image.src = src
                    items.push({
                        src: src,
                        w: image.width || $em2.width,
                        h: image.height || $em2.height,
                        title: title
                    })
                })
                var gallery = new PhotoSwipe(pswpElement, PhotoSwipeUI_Default, items, {
                    index: parseInt(i)
                });
                gallery.init()
            }
        })
    }
    viewer_init()
</script>

<!-- MathJax -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
      tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
  });

  MathJax.Hub.Queue(function() {
      var all = MathJax.Hub.getAllJax(), i;
      for(i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
      }
  });
</script>

<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.6/unpacked/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
  var ayerConfig = {
    mathjax: true
  }
</script>

<!-- Katex -->

<!-- busuanzi  -->


<script src="/js/busuanzi-2.3.pure.min.js"></script>


<!-- ClickLove -->


<script src="/js/clickLove.js"></script>


<!-- ClickBoom1 -->

<!-- ClickBoom2 -->

<!-- CodeCopy -->


<link rel="stylesheet" href="/css/clipboard.css">

<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
  function wait(callback, seconds) {
    var timelag = null;
    timelag = window.setTimeout(callback, seconds);
  }
  !function (e, t, a) {
    var initCopyCode = function(){
      var copyHtml = '';
      copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
      copyHtml += '<i class="ri-file-copy-2-line"></i><span>COPY</span>';
      copyHtml += '</button>';
      $(".highlight .code pre").before(copyHtml);
      $(".article pre code").before(copyHtml);
      var clipboard = new ClipboardJS('.btn-copy', {
        target: function(trigger) {
          return trigger.nextElementSibling;
        }
      });
      clipboard.on('success', function(e) {
        let $btn = $(e.trigger);
        $btn.addClass('copied');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-checkbox-circle-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPIED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-checkbox-circle-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
      clipboard.on('error', function(e) {
        e.clearSelection();
        let $btn = $(e.trigger);
        $btn.addClass('copy-failed');
        let $icon = $($btn.find('i'));
        $icon.removeClass('ri-file-copy-2-line');
        $icon.addClass('ri-time-line');
        let $span = $($btn.find('span'));
        $span[0].innerText = 'COPY FAILED';
        
        wait(function () { // 等待两秒钟后恢复
          $icon.removeClass('ri-time-line');
          $icon.addClass('ri-file-copy-2-line');
          $span[0].innerText = 'COPY';
        }, 2000);
      });
    }
    initCopyCode();
  }(window, document);
</script>


<!-- CanvasBackground -->


<script src="/js/dz.js"></script>



    
  </div>
</body>

</html>